#pragma once
#include <list>
#include <vector>
#include <set>
#include <string>
#include <iostream>
using namespace std;

#include "Vertex.h"
#include "Edge.h"

#include "GraphFather.h"
#include "MiniGraph.h"



class Graph : public GraphFather
{
public: // public data


	Graph (bool directed) : GraphFather (directed)
	{
	}

/*---------------------------------------------------- -------------- ----------------------------*/
/*-------------BAIZOR--------------------------------- Data Functions ----------------------------*/
/*---------------------------------------------------- -------------- ----------------------------*/

	// ...
	// ...
	// From father

/*---------------------------------------------------- -------------------- ----------------------*/
/*-------------BAIZOR--------------------------------- Algorithms Functions ----------------------*/
/*---------------------------------------------------- -------------------- ----------------------*/
	void BFS();
	void DFS();
	bool	MyDFS (Vertex* super_Start_Vertex, Vertex* start_Vertex, Vertex* father_Vertex, int &count);
	DFSType DFS_checkCYCLICAL (Vertex* start_Vertex, Vertex* father) // test: normal (1 test)
	{
		if(start_Vertex -> Type != CLEAR)
			return CYCLICAL;

		start_Vertex -> Type = RED;
		for(int q=0; q<INFINITE_INT; q++)
		{
			Vertex*		goTo = start_Vertex -> goTo(q, Directed);

			if( goTo == NULL)
				break;

			if( goTo == father)
				continue;

			if( DFS_checkCYCLICAL (goTo, start_Vertex) == CYCLICAL)
				return CYCLICAL;
		}

		return NOT_CYCLICAL;
	}


	MiniGraph*	Prima() // test: normal (1 test)
	{
		clearAllVertexesType();

		Edge*	Minimum = getMinimumEdge();

		MiniGraph		*GraphResult	= new MiniGraph (Directed);

		GraphResult -> addNewEdgeAndVertexes(Minimum);

		while (true)
		{
			Minimum = GraphResult -> getMinimumEdgeFromVertexFriends (); 

			if(Minimum == NULL)
				break;

			GraphResult -> addNewEdgeAndVertexes (Minimum);
			GraphResult -> clearAll_New_VertexesType();
			if (DFS_checkCYCLICAL (	*GraphResult -> newBegin(),
									*GraphResult -> newBegin()) == CYCLICAL)
			{
				GraphResult -> CtrlZ();
				break;
			}
		}

		return GraphResult;
	}

	MiniGraph*	Kruskal()
	{
		clearAllVertexesType();

		list <Edge*>				SortingEdges = edges;
		SortingEdges.sort			(qualityCompare_Edge);
		list <Edge*> :: iterator	It		= SortingEdges.begin();

		if (Directed)
		{
			list <Edge*> :: iterator	ItBuf;
			for(int q=1; q<SortingEdges.size(); q++, It++)
			{
				ItBuf = It;
				ItBuf ++;

				for(int w=q; w<SortingEdges.size() && !(**It < **ItBuf) && !(**ItBuf < **It); w++)
				{
					if(**It == **ItBuf)
					{
						ItBuf = SortingEdges.erase (ItBuf);
						w--;
						continue;
					}
					ItBuf++;
				}
			}
			It    = SortingEdges.begin();
		}
		
		MiniGraph		*GraphResult	= new MiniGraph (Directed);

		for(int q=0; q<SortingEdges.size(); q++, It++)
		{
			GraphResult -> addNewEdgeAndVertexes (*It);
			GraphResult -> clearAll_New_VertexesType();
			if (DFS_checkCYCLICAL (	*GraphResult -> newBegin(),
									*GraphResult -> newBegin()) == CYCLICAL)
				GraphResult -> CtrlZ();

			if (GraphResult -> vertexesCount() == vertexesCount())
				break;
		}
		SortingEdges.clear();

		return GraphResult;
	}

	bool EveryVertexCanGoToAny();

/*---------------------------------------------------- ---------- --------------------------------*/
/*-------------BAIZOR--------------------------------- Destructor --------------------------------*/
/*---------------------------------------------------- ---------- --------------------------------*/
	~Graph() // test: good
	{
		list <Vertex*> :: iterator It = vertexes.begin();
		for(int q=0; q<vertexes.size(); q++, It++)
			delete *It;


		list <Edge*> :: iterator It2 = edges.begin();
		for(int q=0; q<edges.size(); q++, It2++)
			delete *It2;
	}
};

// -=BAIZOR=-